import java.util.*;
 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
    TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
        this.left = left;
         this.right = right;
     }
}

public class Test {
    // 题目1 ：杨辉三角Ⅰ
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new LinkedList<>();
        for(int i = 0; i < numRows; i++){
            List<Integer> list = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    list.add(1);
                }else{
                    List<Integer> temp = lists.get(i - 1);
                    list.add(temp.get(j) + temp.get(j - 1));
                }
            }
            lists.add(list);
        }
        return lists;
    }

    // 题目 2 ：杨辉三角Ⅱ
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new LinkedList<>();
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> temp = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    temp.add(1);
                }else{
                    temp.add(list.get(j) + list.get(j - 1));
                }
            }
            list = temp;
        }
        return list;
    }

    // 题目 3：验证搜索二叉树
    public boolean isValidBST1(TreeNode root) {
        return isValidSubBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidSubBST(TreeNode root, long lower, long upper){
        if(root == null){
            return true;
        }

        if(root.val <= lower || root.val >= upper){
            return false;
        }

        return isValidSubBST(root.left, lower, root.val) && isValidSubBST(root.right, root.val, upper);
    }

    Deque<TreeNode> queue = new LinkedList<>();
    public boolean isValidBST0(TreeNode root) {
        if(root == null){
            return true;
        }

        boolean left = isValidBST0(root.left);
        if(!queue.isEmpty()){
            if(root.val <= queue.pollLast().val){
                return false;
            }
        }
        queue.offer(root);
        boolean right = isValidBST0(root.right);
        return left && right;
    }

    public long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }

        if(!isValidBST(root.left)){
            return false;
        }

        if(root.val <= pre){
            return false;
        }

        pre = root.val;

        return isValidBST(root.right);
    }

    public static void main1(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1,6);
        map.put(4,10);
        map.put(2,5);
        List<Integer> list = new LinkedList<>();
        for(Integer x : map.values()){
            list.add(x);
        }
        System.out.println(list.toString());

        List<Integer> list1 = new LinkedList<>();
        for(Integer x : map.keySet()){
            list1.add(x);
        }

        System.out.println(list1.toString());
    }

    // 题目 4：二叉搜索数中的众数
    // 使用哈希表！
    HashMap<Integer, Integer> map = new HashMap<>();
    public int[] findMode1(TreeNode root) {
        inOrder(root);
        List<Integer> list = new LinkedList<>();
        int max = 0;
        for(Integer x : map.values()){
            max = Math.max(x, max);
        }

        for(Integer x : map.keySet()){
            int value = map.get(x);
            if(value == max){
                list.add(x);
            }
        }

        int[] nums = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            nums[i] = list.get(i);
        }
        return nums;
    }

    private void inOrder(TreeNode root){
        if(root == null){
            return ;
        }

        inOrder(root.left);
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        inOrder(root.right);
    }

    // 使用中序遍历！！！来进行优化
    // 中序遍历的话，因为是二叉搜索树，所以重复的元素都集中在一起了。
    List<Integer> list = new LinkedList<>();
    int base, count, maxCount;
    public int[] findMode(TreeNode root) {
        dsf(root);
        int[] ans = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void dsf(TreeNode root){
        if(root == null){
            return ;
        }

        dsf(root.left);
        update(root.val);
        dsf(root.right);
    }

    private void update(int x){
        if(x == base){
            count++;
        }else{
            base = x;
            count = 1;
        }

        if(count == maxCount){
            list.add(base);
        }

        if(count > maxCount){
            list.clear();
            list.add(base);
            maxCount = count;
        }
    }

    // 题目5：平衡二叉树
    // 将 true / false 与 计算树的高度融合起来。
    // -1 为 false，而其余数字代表 true ，也代表树的高度！
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) >= 0 ;
    }

    private int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = getHeight(root.left);
        if(left < 0){
            return -1;
        }

        int right = getHeight(root.right);
        if(right < 0){
            return -1;
        }

        if(Math.abs(left - right) > 1){
            return -1;
        }else{
            return left < right ? right + 1 : left + 1;
        }
    }

    // 题目 6：将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return BST(nums, 0, nums.length - 1);
    }

    private TreeNode BST(int[] nums, int start, int end){
        if(start > end){
            return null;
        }

        int mid = (start + end) / 2;

        TreeNode root = new TreeNode(nums[mid]);

        root.left = BST(nums, start, mid - 1);
        root.right = BST(nums, mid + 1, end);

        return root;
    }

    // 题目7：二叉树的中序遍历
    // 使用了 Morris 遍历
    List<Integer> list1 = new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode cur = root;
        TreeNode mostRight = null;
        while(cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    list1.add(cur.val);
                    mostRight.right = null;
                    cur = cur.right;
                }
            }else{
                list1.add(cur.val);
                cur = cur.right;
            }
        }
        return list1;
    }
}
